/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/minimum-adjustment-cost
@Language: C++
@Datetime: 16-02-09 08:18
*/

class Solution {
public:
    /**
     * @param A: An integer array.
     * @param target: An integer.
     */
    int MinAdjustmentCost(vector<int> A, int target) {
        // write your code here
        int N=A.size();
        if (N<2) return 0;
        vector<vector<int> > DP(N,vector<int>(101,INT_MAX));
        int ans=INT_MAX;
        for(int i=0;i<101;++i)
            DP[0][i]=abs(A[0]-i);
        for(int i=1;i<N;++i)
            for(int j=0;j<101;++j){
                int diff = abs(A[i]-j);
                int start = max(j-target,0);
                int end = min(j+target,100);
                for(int k=start;k<=end;++k)
                    DP[i][j]=min(DP[i][j],DP[i-1][k]+diff);
            }
        for(int i=0;i<101;++i)
            ans=min(ans,DP[N-1][i]);
        return ans;
    }
};